//
// Created by zhou on 2021/10/31.
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int row=matrix.size();
        int col=matrix[0].size();
        vector<vector<int>> dp(row,vector<int>(col));
        int minmun=INT_MAX;
        for(int i=0;i<col;i++){
            dp[0][i]=matrix[0][i];
        }
        if(row==1&&col==1){
            return matrix[0][0];
        }
        for(int i=1;i<row;i++){
            for(int j=0;j<col;j++){
                if(j==0){
                    dp[i][j]=min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i-1][j+1]);
                }
                else if(j==col-1){
                dp[i][j]=min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i-1][j-1]);
                }
                else{
                    dp[i][j]=min(matrix[i][j]+dp[i-1][j],matrix[i][j]+dp[i-1][j-1]);
                    dp[i][j]=min(dp[i][j],matrix[i][j]+dp[i-1][j+1]);
                }
            }
        }

        return *min_element(dp[row-1].begin(),dp[row-1].end());
    }
};
int main(){
    Solution solution;
    vector<vector<int>> matrix={
            {1,2,3},
            {2,4,-1},
            {3,-2,9}
    };
    cout<<solution.minFallingPathSum(matrix);
}